package Lagou.Stack;

import java.util.Stack;

/**
 *例 1：判断字符串括号是否合法
 * 【题目】字符串中只有字符'('和')'。合法字符串需要括号可以配对。
 *比如：
 * 输入："()"
 * 输出：true
 **/
class Stack01 {
    //方法一 利用栈
    boolean isValid1(String s) {
        //字符串为空
        if (s == null || s.length() == 0) return true;
        //字符串长度为奇数
        if (s.length() % 2 == 1) return false;
        //采用栈进行消除
        Stack<Character> t = new Stack<Character>();
        for (int i = 0; i <s.length(); i++) {
            //取出字符
            char c = s.charAt(i);
            if (c == '(') {
                //压栈
                t.push(c);
            }else if (c == ')') {
                //弹栈
                if (t.empty()) {
                    return false;
                }
                t.pop();
            }
        }
        return t.empty();
    }

    //方法二 采用计数的思想
    //栈中元素都相同时，实际上没有必要使用栈，只需要记录栈中元素个数。
    public boolean isvalid2(String s) {
        //字符串为空
        if (s == null || s.length() == 0) return true;
        //字符串长度为奇数
        if (s.length() % 2 == 1)  return false;

        int leftBraceNumber = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftBraceNumber++;
            }else if (c == ')') {
                if (leftBraceNumber <= 0){
                    return false;
                }
                --leftBraceNumber;
            }
        }
        return leftBraceNumber == 0;
    }

    //题目扩展
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，
     * 判断字符串是否有效。有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合
     * 左括号必须以正确的顺序闭合
     * 注意空字符串可被认为是有效字符串
     * **/
    public boolean isValid3(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (s.length() % 2 == 1) {
            return false;
        }
        Stack<Character> t = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '(' || c == '[') {
                t.push(c);
            } else if (c == '}') {
                if (t.empty() || t.peek() != '{') {
                    return false;
                }
                t.pop();
            } else if (c == ']') {
                if (t.empty() || t.peek() != '[') {
                    return false;
                }
                t.pop();
            } else if (c == ')') {
                if (t.empty() || t.peek() != '(') {
                    return false;
                }
                t.pop();
            } else {
                return false;
            }
        }

        return t.empty();
    }
}
